package com.origin.niuke.tree;

import general_class.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * NC223 从中序与后序遍历序列构造二叉树
 * 算法；二叉树
 *
 * @author yezh
 * @date 2022/11/26 18:16
 */
public class NC223 {

    public static void main(String[] args) {
        System.out.println(new NC223().buildTree(new int[]{1, 10, 100, 1000, 10000, 1000000000, 100000}, new int[]{1000000000, 100000, 10000, 1000, 100, 10, 1}));
    }

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        // write code here
        int n = inorder.length;
        Map<Integer, Integer> inorderMap = new HashMap<>(n);
        for (int i = 0; i < n; i++) inorderMap.put(inorder[i], i);
        return buildTree(0, n - 1, 0, inorderMap, postorder);
    }

    TreeNode buildTree(int begin, int end, int inBegin, Map<Integer, Integer> inorderMap, int[] postorder) {
        if (begin > end) return null;
        TreeNode node = new TreeNode(postorder[end]);
        int idx = inorderMap.get(postorder[end]);
        int leftNum = idx - inBegin;
        node.left = buildTree(begin, begin + leftNum - 1, inBegin, inorderMap, postorder);
        node.right = buildTree(begin + leftNum, end - 1, idx + 1, inorderMap, postorder);
        return node;
    }

}
